#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*- 
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab 
# http://www.careercup.com/question?id=11532811
"""
Given an array A[], find (i, j) such that A[i] < A[j] and (j - i) is maximum.
"""
from utils import *

@time_profile
def find_max_diff_david(A):
    if not A: return (0, 0)
    length = len(A)
    pre_sequences = [(A[0], 0)]
    suf_sequences = [(A[-1], length - 1)]
    for i in range(1, length):
        if A[i] < pre_sequences[-1][0]: pre_sequences.append((A[i], i))
    for i in range(length - 2, -1, -1):
        if A[i] > suf_sequences[-1][0]: suf_sequences.append((A[i], i))
    result = (-1, -1)
    for i in range(0, len(pre_sequences)):
        if result[1] - result[0] >= suf_sequences[0][1] - pre_sequences[i][1]: break
        for suffix in suf_sequences:
            if suffix[0] > pre_sequences[i][0]:
                if suffix[1] - pre_sequences[i][1] > result[1] - result[0]: result = (pre_sequences[i][1], suffix[1])
                break
    return result
    

@time_profile
def find_max_diff_lobatt(A):
    maxdiff = len(A) - 1
    for step in range(maxdiff, 0, -1):
        for i in range(0, len(A) - step):
            if A[step + i] > A[i]: return (i, step + i)
    return (-1, -1)
    
@time_profile
def find_max_diff_baseline(A):
    maxdiff,ti, tj = -1, -1, -1
    for i in range(0, len(A)):
        for j in range(i, len(A)):
            if A[j] > A[i] and j - i > maxdiff:
                maxdiff = j - i
                ti = i
                tj = j
    return (ti, tj)

   

if __name__ == '__main__':
    #Bad case below, what is the proper return value?
    #A = range(10000, 0, -1)
    A = random_arr(10000, 0, 10000)
    
    r1 = find_max_diff_david(A)
    r2 = find_max_diff_lobatt(A)
    r3 = find_max_diff_baseline(A)
    if r1 == r2 and r2 == r3: print_pass()
    else:
        print_fail()
        print A
        print r1
        print r2
